import org.junit.jupiter.api.Test;

public class _33_搜索旋转排序数组_二分查找 {
    @Test
    public void test(){
        int []arr={5,1,2,3,4};
        System.out.println(search(arr, 1));
    }

    public int search(int[] nums, int target) {
        if (nums.length==0) return -1;
        if (nums.length==1) return nums[0]==target?1:-1;
        int left=0;
        int right=nums.length-1;


        while (left<=right){
            int mid=left+(right-left)/2;
            int leftVal=nums[left];
            int rightVal=nums[right];
            int midVal=nums[mid];
            if (leftVal==target) return left;
            if (midVal==target) return mid;
            if (rightVal==target) return  right;
            if (midVal>rightVal){
                //左边是有序的
                if (target>leftVal&&target<midVal){
                    //目标值在左边有序区域
                    left=left+1;
                    right=mid-1;
                }else {
                    //目标值在右边无序区域
                    left=mid+1;
                    right=right-1;
                }
            }else {
                //右边的区域是有序的
                if (target>midVal&&target<rightVal){
                    //目标值在右边有序区域
                    left=mid+1;
                    right=right-1;
                }else {
                    //目标值在左边无序区域
                    right=mid-1;
                    left=left+1;
                }
            }
        }
        return -1;
    }

}
